#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);
        int last[10];
        memset(last, -1, 10 * sizeof(int));
        for (int i = 0; i < str.size(); ++i) {
            last[str[i] - '0'] = i;
        }
        for (int i = 0; i < str.size(); ++i) {
            for (int j = 9; j > str[i]-'0'; --j) {
                if (last[j] > i) {
                    swap(str[i], str[last[j]]);
                    return atoi(str.c_str());
                }
            }
        }
        return num;
    }
};